package com.tucc.hello.leetcode.no801_1200.no1049;

import java.util.Arrays;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution_bad {

    public static void main(String[] args) {
        Solution_bad solution = new Solution_bad();
        int[] stones = {2, 7, 4, 1, 8, 1};
        System.out.println(solution.lastStoneWeightII(stones));
        solution.printArr(stones);
    }

    /**
     * 输入：stones = [2,7,4,1,8,1]
     * 输出：1
     * 解释：
     * 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
     * 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
     * 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
     * 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
     */
    public int lastStoneWeightII(int[] stones) {
        lastStoneWeightII(stones, stones.length);
        return min;
    }

    int min = Integer.MAX_VALUE;

    public void lastStoneWeightII(int[] stones, int size) {
        if (stones.length == 0) {
            return;
        }
        if (stones.length == 1) {
            min = Math.min(stones[0], min);
            return;
        }
        if (size == 2) {
            int abs = Math.abs(stones[0] - stones[1]);
            min = Math.min(abs, min);
            return;
        }

        for (int i = 0; i < size - 1; i++) {
            for(int j = i + 1;j < size;j ++) {
                int a = stones[i];
                int b = stones[j];
                int abs = Math.abs(a - b);
                if (abs == 0) {
//                    swap(stones, size - 1, i);
//                    swap(stones, size - 2, j);
                    int[] newArr = new int[size - 2];
                    int len0 = i;
                    if(len0 > 0){
                        System.arraycopy(stones, 0, newArr, 0, len0);
                    }
                    int len1 = j - i - 1;
                    if(len1 > 0) {
                        System.arraycopy(stones, i + 1, newArr, len0, len1);
                    }
                    int len2 = size - j - 1;
                    if(len2 > 0) {
                        System.arraycopy(stones, j + 1, newArr, len0 + len1, len2);
                    }
//                printArr(stones);
                    lastStoneWeightII(newArr, size - 2);
//                    System.out.print("size :" + size + "  ");
//                    printArr(stones);
//                    swap(stones, size - 1, i);
//                    swap(stones, size - 2, j);
//                printArr(stones);
                } else {
//                    swap(stones, size - 1, i);
//                    stones[j] = abs;
//                printArr(stones);
                    int[] newArr = new int[size - 1];
                    int len1 = j - i - 1;
                    int len0 = i;
                    if(len0 > 0){
                        System.arraycopy(stones, 0, newArr, 1, len0);
                    }
                    if(len1 > 0) {
                        System.arraycopy(stones, i + 1, newArr, len0 + 1, len1);
                    }
                    int len2 = size - j - 1;
                    if(len2 > 0) {
                        System.arraycopy(stones, j + 1, newArr, len0 + len1 + 1, len2);
                    }
                    newArr[0] = abs;
                    lastStoneWeightII(newArr, size - 1);

//                    System.out.print("size :" + size + "  ");
//                    printArr(stones);
//                    swap(stones, size - 1, i);
//                    stones[j] = b;

//                printArr(stones);
                }
            }
        }
    }


    public void swap(int[] arr, int x, int y) {
        if (x != y) {
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
    }

    private void printArr(int[] arr){
        Arrays.stream(arr).mapToObj(o -> o + " ").forEach(System.out::print);
        System.out.println();
    }

}
